/*
 * @lc app=leetcode.cn id=93313 lang=javascript
 *
 * [面试题 17.21] 直方图的水量
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  /**
   * 单调栈
   * @param {number[]} height
   * @return {number}
   */
  var trap = function (height) {
    const size = height.length;

    if (size < 3) return 0;
    // 栈底到栈顶的单调递增，存储下标
    const stack = [];
    let result = 0;
    for (let i = 0; i < size; i++) {
      // 栈顶小于当前元素时候，如果栈内元素最少为2个，height[栈顶-1]>height[栈顶]<height[当前元素]
      // 这样才会形成一个凹槽，来接水
      while (stack.length && height[i] > height[stack[stack.length - 1]]) {
        let mid = stack.pop();
        if (stack.length) {
          let left = stack[stack.length - 1];
          let w = i - left + 1 - 2;
          let h = Math.min(height[left], height[i]) - height[mid];
          result += w * h;
        }
      }
      stack.push(i);
    }

    return result;
  };
};
// @lc code=end
